Nombres de Mersenne - Corrigé

Énoncé

Pour tout entier \(n \geqslant 2\) , on pose \(M_n=2^n-1\) , appelé \(n\) -ème nombre de Mersenne.

1. a. Calculer  \(M_2\) , \(M_3\) ,  \(M_4\) ,  \(M_5\) ,  \(M_6\) ,  \(M_7\) et \(M_8\) .
    b. Parmi les nombres de Mersenne calculés précédemment, lesquels sont premiers ?

2. On souhaite démontrer que, étant donné un entier  \(n \geqslant 2\) , si  \(M_n\)  est un nombre premier, alors  \(n\)  est aussi un nombre premier.
    a. Soit  \(n \geqslant 2\)  et  \(a\) ,  \(b \in \mathbb{Z}\) .
Montrer que  \(a^n-b^n=(a-b)\left(b^{n-1}+ab^{n-2}+a^2b^{n-3}+...+a^{n-2}b+a^{n-1}\right)\) .
    b. Soit \(n \geqslant 2\) un entier non premier.
Justifier qu'il existe un nombre premier \(p \geqslant 2\) et un entier \(m \geqslant 2\) tels que \(n=pm\) ,
puis montrer que  \(M_n=(2^p-1)(1+2^p+(2^p)^2+...+(2^p)^{m-1})\) .
    c. Conclure.

3. Démontrer que la réciproque de la propriété prouvée à la question 2 est fausse, c'est-à-dire que si \(n\) est un nombre premier, alors \(M_n\) n'est pas nécessairement un nombre premier.

Solution

1. On a

• \(M_2=2^2-1=4-1=3\) ;
  
• \(M_3=2^3-1=8-1=7\)  ;
  
• \(M_4=2^4-1=16-1=15\)  ;
  
• \(M_5=2^5-1=32-1=31\)  ;
  
• \(M_6=2^6-1=64-1=63\)  ;
  
• \(M_7=2^7-1=128-1=127\)  ;
  
• \(M_8=2^8-1=256-1=255\) .
  

b. On remarque que les nombres  \(M_2\) ,  \(M_3\) ,  \(M_5\)  et  \(M_7\)  sont premiers, à l'inverse des autres qui ont été calculés. Il semble que  \(M_n\) est premier lorsque  \(n\)  est premier.

2. a. On a
\(\begin{align*}(a-b)\left(b^{n-1}+ab^{n-1}+a^2b^{n-3}+...+a^{n-2}b+a^{n-1}\right)& = (a-b) \times \sum_{k=0}^{n-1} a^kb^{n-1-k}\\& = \sum_{k=0}^{n-1} a^{k+1}b^{n-1-k} - \sum_{k=0}^{n-1} a^kb^{n-k}\\& = \sum_{k=1}^{n} a^kb^{n-k} - \sum_{k=0}^{n-1} a^kb^{n-k}\\& = a^nb^0 - a^0b^n\\& = a^n-b^n\end{align*}\)    
  donc  \(a^n-b^n=(a-b)\left(b^{n-1}+ab^{n-2}+a^2b^{n-3}+...+a^{n-2}b+a^{n-1}\right)\) .

b. Comme  \(n\)  est un entier supérieur ou égal à  \(2\) , il possède un diviseur premier  \(p \geqslant 2\) , c'est-à-dire que l'on peut écrire  \(n=pm\)  avec  \(m \in \mathbb{N}\) . De plus, il est clair que  \(m \neq 0\)  (sinon  \(n\)  serait égal à  \(0\) ) et que  \(m \neq 1\)  (sinon  \(n\)  serait égal à  \(p\) , qui est premier alors que  \(n\)  ne l'est pas), et ainsi \(m \geqslant 2\) .
Comme  \(M_n=2^n-1=2^{pm}-1=(2^p)^m-1^m\) , on peut alors appliquer le résultat de la question 2.a avec  \(n=m\) ,  \(a=2^p\)  et  \(b=1\)  :
\(\begin{align*}M_n& =(2^p)^m-1^m \\ & = (2^p-1)\left(1^{m-1}+2^p \times 1^{m-2}+(2^p)^2 \times 1^{m-3}+...+(2^p)^{m-2} \times 1+(2^p)^{m-1}\right) \\ & = (2^p-1)\left(1+2^p+(2^p)^2+...+(2^p)^{m-2}+(2^p)^{m-1}\right)\end{align*}\)  
et donc  \(M_n=(2^p-1)(1+2^p+(2^p)^2+...+(2^p)^{m-1})\) .

c. Soit \(n \geqslant 2\)  un entier. Supposons que \(M_n\) est un nombre premier.
Raisonnons par l'absurde, et supposons que \(n\) n'est pas premier. D'après la question 2.b, on peut écrire  \(n=pm\) avec \(p \geqslant 2\) premier et \(m \geqslant 2\) , et de plus,  \(2^p-1\)  divise  \(M_n\) .

Or \(M_n\) est premier, donc

• soit \(2^p-1=1\) , c'est-à-dire \(2^p=2\) et donc \(p=1\) : absurde car \(p \geqslant 2\) ;
• soit \(2^p-1=M_n=2^n-1\) , c'est-à-dire \(2^p=2^n\) et donc \(p=n\) : absurde car \(p\) est premier tandis que  \(n\) ne l'est pas.

Par conséquent, \(n\) est premier.

3. On remarque que \(M_{11}=2^{11}-1=2047=23 \times 89\) n'est pas premier, alors que \(11\) est premier.

Remarque

Il existe un test de primalité efficace adapté aux nombres de Mersenne, ce qui fait que les plus grands nombres premiers connus sont des nombres de Mersenne.
Aujourd'hui, on connaît 51 nombres premiers parmi les nombres de Mersenne.